あの雲も越えてゆけ
遠くまだ遠くまで
遠くまだ遠くまで
Day0
打了一天的板子。吃完晚饭后去杭州，给我校所有选手都买了瓶饮料希望能攒 RP。
Day1
晚上被室友呼噜吵醒了，响得要死根本睡不着。
早上醒来肚子痛，在酒店上了一次厕所，进考场前又上了一次，debuff 拉满了。
考场左前方是 lhx。
开考先把三个题都看了一遍，T2 看起来是个什么比较暴力的数据结构，T3 感觉不太可做。
T1 稍微玩了一会就会了，很快写完过掉样例，只用了半个小时。
然后做 T2，仔细读了一遍题，发现图没有任何性质（甚至没看到 u<vu < vu<v），那复杂度至少是 O(nmw)O(\frac{nm}{w})O(wnm) 了，毛猜猜是什么四毛子状物。想到了一些传递闭包的神秘剖分之类的东西，可以在图上加点维护传递闭包，然后就要维护每个时刻的信息进行查询。尝试了一下，发现首先块长只能取很小而且没办法方便修改，然后尝试改进做法，搞了一会发现可以对每个块二分出 aaa 在范围内的集合，然后再二分出答案，这样块长就可以开到 www 了，修改直接暴力重构两个块，复杂度是 O(nqwlogw)O(\frac{nq}{w}\log w)O(w...
为啥这玩意没在 OI 中普及啊？
Description
有 nnn 种物品，第 iii 种物品的重量为 wiw_iwi，价值为 viv_ivi，一共有 cic_ici 个，求在总重量不超过 mmm 时的价值之和最大是多少。
形式化地，求：
max∑i=1nxivis.t.{∀1≤i≤n,xi∈Z∧0≤xi≤ci∑i=1nxiwi≤m\max \sum\limits_{i = 1}^n x_i v_i \\
\text{s.t.}
\begin{cases}
\forall 1 \le i \le n, x_i \in \mathbb{Z} \land 0 \le x_i \le c_i \\
\sum_{i = 1}^n x_i w_i \le m
\end{cases}
maxi=1∑nxivis.t.{∀1≤i≤n,xi∈Z∧0≤xi≤ci∑i=1nxiwi≤m
其中 1≤wi≤W1 \le w_i \le W1≤wi≤W
我们有一个 O(nlogn+W3logW)O(n \log n + W^3 \log W)O(nlogn+W3lo...
PKUWC
Day 1
早上 7:40 起床，爽睡了。
路上 wc 跟我说只有我没到了，仔细一问原来我听错集合时间了，这下爆蛋了。最后迟了大概 7 分钟才到。
报道完在边上随机游走，cyf 带着 zxx 来和 zyz 面基，我在旁边有点尴尬就偷偷润了。
在报道厅里面到了那老师和 Meatherm。还收到了 Mea 的徽章。大家都好帅啊。
开幕式没啥好说的。午饭还行，不是绍一食堂承包，应该没有卫生问题。
吃完饭回报告厅开了一会 Phigros，然后背了下板子，没记住。
进考场试机，配了下 VSCode。看眼试机题，怎么是我玉玉症题，skip。第二题不会做，懒得想了，默写了一下 NTT。
开始之后先看 T1，感觉不太会做。看眼 T2，数据结构。再看 T3，看着好眼熟，但是没啥想法。
继续做 T1，没啥想法，先猜了个 a>b+1a > b + 1a>b+1 的结论，交上去发现假了，有点急。仔细想了一下，发现本质上是构造一个 a+ba + ba+b 个点的图使得最大独立集只有 a−1a - 1a−1。
这数据范围铁 O(T(a+b)+(a+b)2)O(T(a + ...
对于一些算法，如果我们可以将其视作对一个向量的若干线性变换，则称这种算法为线性算法。
具体地，我们可以将算法过程中维护的变量写成一个向量 v⃗\vec{v}v，然后如果对这些变量的操作都是在向量上的线性变换，那么这就是一个线性算法。
把线性变换写作一个矩阵 AAA，就可以将该算法表示为矩阵与向量的乘法 A×v⃗A \times \vec{v}A×v。
我们称 ATv⃗A^T \vec{v}ATv 为这个算法的转置算法。
但是我们显然不能把矩阵 AAA 给直接写出来，因此需要考虑如何快速得到转置算法。
首先把矩阵 AAA 拆成若干个初等矩阵相乘的形式：A=BkBk−1…B1A = B_k B_{k - 1} \ldots B_1A=BkBk−1…B1，于是就有：
BkBk−1…B1v⃗=B1TB2T…BkTv⃗B_k B_{k - 1} \ldots B_1 \vec{v} = B_1^T B_2^T \ldots B_k^T \vec{v}BkBk−1…B1v=B1TB2T…BkTv
这样就相当于把所有初等变换的顺序倒过来然后把每个初等变换转置一下，于是我们只需...
从 k 总那里搞到了个名额，CSP 是爆蛋了，还是看看远处的南京站吧。
Day -?
发了参赛手册，看了几眼，发现有很多 sxyz 毕业选手 & 发现左边是 nfls 队伍，害怕。
Day 0
早上去 sxyz 接 pi 老师，然后上高铁去南京。高铁上和队友练了会兵。
排队签到的时候看到了赤橙黄绿青蓝紫。
排完肚子饿死了，就先去吃了个饭，吃完被告知还要去领 kkk 的衣服……
等衣服领完去领集赞的奖品就只剩暖手宝了……
然后把 kkk 的衣服交给 panda，顺便拿了 hydro 的徽章，然后去食堂找了 zjc。
下午开幕式发现座位比较阴间，主席台方向屁也看不到。
热身赛队友慢速过了 B，然后我慢速过了 C，然后发现 E 是之前 VP 过的去年南京站，光速写了一下，过掉之后队友说 AD 都会完了，我直接开摆！
然后去看了下 zjc、zqy 和 yk，回来队友告诉我 A 题做法假了？我看了下大概胡了个每次从一个点追另一个点，然后等队友把 D 写完，最后 D 也没过……
其实还去远远地偷看了一下 szm & sk & madoka 队，但是因为社恐所以瞄了...